package shellSort;

public class ShellSort {

	public static void main(String[] args) {
		int[] a = { 3, 5, 8, 1, 6, 2, 0, 7, 4, 9, -1, 2 };
		for (int d = a.length / 2; d >= 1; d = d / 2) {// d标识的是步长，第一次步长为数组的一半，第二次为上一次的一半，依次……
			for (int i = d; i < a.length; i = i + 1) {// 依次选定步长来排序,采用插入排序的方式。
				if (a[i - d] > a[i]) {
					int temp = a[i];
					int j = i - d;
					for (; j >= 0; j = j - d) {// 这里是一个步长为d的直接插入排序
						if (a[j] > temp) {
							a[j + d] = a[j];
						} else {
							break;
						}
					}
					a[j + d] = temp;
				}
			}
		}
		printArray(a);
	}

	/**
	 * 打印输出数组a到控制台
	 * 
	 * @param a
	 */
	private static void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "\t");
		}
	}

	/**
	 * 交换数组中两个位置的值
	 * 
	 * @param a
	 * @param i
	 * @param index
	 */
	private static void swap(int[] a, int i, int index) {
		int temp = 0;
		temp = a[i];
		a[i] = a[index];
		a[index] = temp;
	}

}
